package binary_tree.LeetCode;

import java.util.HashMap;
import java.util.Map;

public class Num106 {
    Map<Integer,Integer> map=new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
     int[] preorder=reverse( inorder, postorder);
     return buildTreeInternal(inorder,preorder,0,preorder.length);
    }
    int index=0;
    public TreeNode buildTreeInternal(int[] inorder,int[] postorder,int left,int right){
    if(left>=right){
        return null;
    }
    if(index>= postorder.length){
        return null;
    }
    TreeNode root=new TreeNode(postorder[index]);
    index++;
    int pos= map.get(root.val);
    root.right=buildTreeInternal(inorder,postorder,pos+1,right);
    root.left=buildTreeInternal(inorder,postorder,left,pos);
    return root;
    }

    private int[] reverse(int[] inorder,int[] postorder){
        int[] ret=new int[postorder.length];
        for(int i=0;i<ret.length;i++){
            ret[i]=postorder[ret.length-1-i];
        }
        for(int i=0;i< inorder.length;i++){
            map.put(inorder[i],i);
        }
        return ret;
    }
}
